#ifndef UUID_EFB7C44C065549336698C6B53A480018
#define UUID_EFB7C44C065549336698C6B53A480018

#include <cassert>
#include <cstdio>

#include "common.hpp"

int const QSModelTableShift = 7;
int const QSModelSearchSize = (1<<QSModelTableShift) + 1;
int const QSModelLogTot = 14;
int const QSModelSearchShift = QSModelLogTot - QSModelTableShift;

template<int N>
struct QSModel
{
	QSModel()
	{
		cf[N] = 1<<QSModelLogTot;
		cf[0] = 0;
		search[1<<QSModelTableShift] = N - 1;
		targetrescale = 1<<12;

		reset();
	}

	void reset()
	{
		rescale = (N >> 4) | 2;
		left = nextleft = 0;

		int initval = cf[N] / N;
		int end = cf[N] % N;

		for(int i = 0; i < end; ++i)
			newf[i] = initval + 1;
		for(int i = end; i < N; ++i)
			newf[i] = initval;
	}

	void dorescale(bool updateSearch = false)
	{
		if(nextleft)
		{
			++incr;
			left = nextleft;
			nextleft = 0;
			return;
		}

		if (rescale < targetrescale)  /* double rescale interval if needed */
		{   rescale <<= 1;
			if (rescale > targetrescale)
				rescale = targetrescale;
		}

		int sum = cf[N];
		int missing = sum;
		
		for(int i = N - 1; i; --i)
		{
			int tmp = newf[i];
			sum -= tmp;
			cf[i] = sum;
			tmp = tmp>>1 | 1;
			missing -= tmp;
			newf[i] = tmp;
		}

		/*
		if (cf!=m->newf[0])
		{   fprintf(stderr,"BUG: rescaling left %d total frequency\n",cf);
			deleteqsmodel(m);
			exit(1);
		}*/

		assert(sum == newf[0]);

		newf[0] = newf[0]>>1 | 1;
		missing -= newf[0];
		incr = missing / rescale;
		nextleft = missing % rescale;
		left = rescale - nextleft;

		if(updateSearch)
		{
			int i = N;
			while (i)
			{
				int end = (cf[i]-1) >> QSModelSearchShift;
				i--;
				int start = cf[i] >> QSModelSearchShift;

				while(start <= end)
				{
					search[start++] = i;
				}
			}
		}
	}

	template<typename Coder>
	void encode(Coder& e, int sym)
	{
		check_update(false);
		uint32 base = cf[sym];
		uint32 size = cf[sym + 1] - base;

		e.encode_shift(base, size, QSModelLogTot);
		update(sym);
	}

	template<typename Decoder>
	int decode(Decoder& e)
	{
		check_update(true);
		uint32 cnt = e.get_count_shift(QSModelLogTot);

		uint16* tmp = &search[cnt >> QSModelSearchShift];

		int lo = tmp[0];
		int hi = tmp[1] + 1;

		while(lo + 1 < hi)
		{
			int mid = (lo + hi) >> 1;
			if(cnt < cf[mid])
				hi = mid;
			else
				lo = mid;
		}

		uint32 base = cf[lo];
		uint32 size = cf[lo + 1] - base;

		e.decoded_range(base, size);
		update(lo);
		return lo;
	}

	void check_update(bool updateSearch)
	{
		if(left <= 0)
			dorescale(updateSearch);
	}

	void update(int sym)
	{
		--left;
		newf[sym] += incr;
	}

	int left, nextleft, incr, rescale, targetrescale;

	uint16 cf[N+1], newf[N+1];
	uint16 search[QSModelSearchSize];
};

#endif // UUID_EFB7C44C065549336698C6B53A480018
